//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "type_traits.h"
#include "algobase.h"
#include "memory.h"
#include "forward.h"

FC_NAMESPACE_BEGIN


template <class T, size_t N>
class static_vector
{
public:
	typedef static_vector<T, N>			this_type;
	typedef size_t						size_type;
	typedef T							value_type;
	typedef T*							pointer;
	typedef const T*					const_pointer;
	typedef T&							reference;
	typedef const T&					const_reference;
	typedef T*							iterator;
	typedef const T*					const_iterator;

	typedef aligned_buffer<(N * sizeof(T)), FC_ALIGNOF(T)> buffer_type;

	static_vector()
		: m_size(0)
		{
		}

	static_vector( size_t n, const T& value )
		: m_size(0)
		{
			assign_n( n, value );
		}

	template <class InputIterator>
	static_vector( InputIterator first, InputIterator last )
		: m_size(0)
		{
			assign( first, last );
		}

	static_vector( const this_type& x )
		: m_size(0)
		{
			assign_iter( x.begin(), x.end() );
		}

	~static_vector()
		{
			clear();
		}

	bool empty() const				{ return m_size == 0; }
	bool full() const				{ return m_size == N; }
	size_t capacity() const			{ return N; }
	size_t max_size() const			{ return N; }
	size_t unused() const			{ return N - m_size; }
	size_t size() const				{ return m_size; }
	iterator begin()				{ return (T*)m_buffer.data; }
	const_iterator begin() const	{ return (T*)m_buffer.data; }
	iterator end()					{ return begin() + m_size; }
	const_iterator end() const		{ return begin() + m_size; }
	const_iterator cbegin() const	{ return (T*)m_buffer.data; }
	const_iterator cend() const		{ return begin() + m_size; }
	pointer data()					{ return (T*)m_buffer.data; }
	const_pointer data() const		{ return (T*)m_buffer.data; }
	reference front()				{ return operator [](0); }
	const_reference front() const	{ return operator [](0); }
	reference back()				{ return operator [](m_size - 1); }
	const_reference back() const	{ return operator [](m_size - 1); }

	reference operator []( size_t i ) { return *(((T*)m_buffer.data) + i); }
	const_reference operator []( size_t i ) const { return *(((T*)m_buffer.data) + i); }

	reference at( size_t i )
	{
		FC_ASSERT(i < m_size);
		return *(((T*)m_buffer.data) + i);
	}

	const_reference at( size_t i ) const
	{
		FC_ASSERT(i < m_size);
		return *(((T*)m_buffer.data) + i);
	}

	void reserve( size_t ) {}
	void reset() { m_size = 0; }
	void clear()
	{
		fc::destroy_n(begin(), m_size);
		m_size = 0;
	}

	void resize( size_t n, const T& value = T() )
	{
		FC_ASSERT(n <= N);
		if( n > m_size )
		{
			fc::fill_n( end(), n - m_size, value );
			m_size = n;
		}
		else if( n < m_size )
			erase( begin() + n, end() );
	}

	void assign( size_t n, const T& value ) { assign_n( n, value ); }
	void assign_n( size_t n, const T& value )
	{
		AssignValues( n, value, typename is_pod<T>::type() );
	}

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		AssignDispatch( first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class ForwardIterator>
	void assign_iter( ForwardIterator first, ForwardIterator last )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	void insert_at( size_t pos, const T& value ) { insert( begin() + pos, value ); }
	void insert_at( size_t pos, size_t n, const T& value ) { insert_n( begin() + pos, n, value ); }

	iterator insert( iterator pos, const T& value )
	{
		FC_ASSERT(iterator_is_valid(it));

		if( pos == (T*)m_buffer.data + m_size )
		{
			fc::construct( ((T*)m_buffer.data) + (m_size++), value );
		}
		else
		{
			// avoid making a copy of unknown type if value is in range
			const T* ptrVal = &value;
			if( (ptrVal >= pos) && (ptrVal < end()) )
				++ptrVal;

			T* last = end() - 1;
			fc::construct( end(), *(last) );
			fc::copy_backward( pos, last, end() );
			*pos = *ptrVal;
			++m_size;
		}

		return pos;
	}

	inline void insert( iterator pos, size_t n, const T& value )
	{
		InsertValues( pos, n, value,
			typename is_pod<T>::type() );
	}

	inline void insert_n( iterator pos, size_t n, const T& value )
	{
		InsertValues( pos, n, value,
			typename is_pod<T>::type() );
	}

	template <class InputIterator> inline
	void insert( iterator pos, InputIterator first, InputIterator last )
	{
		InsertDispatch( pos, first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class InputIterator> inline
	void insert_iter( iterator pos, InputIterator first, InputIterator last )
	{
		InsertIterator( pos, first, last,
			typename is_pod<InputIterator>::type() );
	}

	iterator erase( iterator pos )
	{
		FC_ASSERT(pos >= begin() && pos < end());

		fc::copy( pos + 1, end(), pos );
		fc::destroy( begin() + --m_size );

		return pos;
	}

	iterator erase( iterator first, iterator last )
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last));
		FC_ASSERT(first <= last);

		T* ptr = fc::copy( last, end(), first );
		fc::destroy_range( ptr, end() );
		m_size -= size_t(last - first);

		return first;
	}

	iterator erase_unordered( iterator pos )
	{
		FC_ASSERT(pos >= begin() && pos < end());

		--m_size;
		*pos = begin() + m_size;
		fc::destroy( begin() + m_size );

		return pos;
	}

	void erase_unordered_at( size_t pos ) { erase_unordered( begin() + pos ); }
	void erase_at( size_t pos ) { erase( begin() + pos ); }
	void erase_at( size_t pos, size_t n ) { erase( begin() + pos, begin() + pos + n ); }

	void push_back( const T& value = T() )
	{
		FC_ASSERT(m_size < N);
		fc::construct( ((T*)m_buffer.data) + (m_size++), value );
	}

	T* push_back_uninitialized( size_t n = 1 )
	{
		FC_ASSERT(m_size + n <= N);
		m_size += n;
		return (((T*)m_buffer.data) + (m_size - n));
	}

	void pop_back()
	{
		FC_ASSERT(!empty());
		fc::destroy( ((T*)m_buffer.data) + (--m_size) );
	}

	void push_front( const T& value = T() ) { insert( begin(), value ); }
	void pop_front() { erase(begin()); }

	this_type& operator =( const this_type& x )
	{
		if( this != &x )
			assign_iter( x.begin(), x.end() );
		return *this;
	}

	bool iterator_is_valid( const_iterator it ) const
	{
		return (it >= begin() && it <= end());
	}


protected:
	template <class InputIterator>
	inline void AssignDispatch( InputIterator first, InputIterator last, const false_type& )
	{
		AssignIterator( first, last, typename is_pod<T>::type() );
	}

	template <class Integral>
	inline void AssignDispatch( Integral n, Integral value, const true_type& )
	{
		AssignValues( (size_t)n, (T)value, typename is_pod<T>::type() );
	}

	template <class InputIterator>
	inline void InsertDispatch( iterator pos, InputIterator first, InputIterator last, const false_type& )
	{
		InsertIterator( pos, first, last, typename is_pod<T>::type() );
	}

	template <class Integral>
	inline void InsertDispatch( iterator pos, Integral n, Integral value, const true_type& )
	{
		InsertValues( pos, n, value, typename is_pod<T>::type() );
	}

	void AssignValues( size_t n, const T& value, true_type )
	{
		n = fc::min(n, N);
		fc::fill_n( begin(), n, value );
		m_size = n;
	}

	void AssignValues( size_t n, const T& value, false_type )
	{
		n = fc::min(n, N);
		if( n > m_size )
		{
			fc::fill( begin(), end(), value );
			fc::uninitialized_fill( end(), begin() + n, value );
			m_size = n;
		}
		else
		{
			fc::fill_n( begin(), n, value );
			erase( begin() + n, end() );
		}
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, true_type )
	{
		const size_t n = fc::min( N, (size_t)fc::distance(first, last) );
		ForwardIterator newLast = first;
		fc::advance( newLast, n );
		fc::copy( first, newLast, begin() );
		m_size = n;
	}

	template <class ForwardIterator>
	void AssignIterator( ForwardIterator first, ForwardIterator last, false_type )
	{
		const size_t n = fc::min( N, (size_t)fc::distance(first, last) );
		if( n > m_size )
		{
			ForwardIterator mid = first;
			fc::advance( mid, m_size );
			fc::uninitialized_copy( mid, last, fc::copy(first, mid, begin()) );
		}
		else
		{
			fc::copy( first, last, begin() );
			fc::destroy_range( begin() + n, end() );
		}
		m_size = n;
	}

	template <class ForwardIterator>
	void InsertIterator( iterator pos, ForwardIterator first, ForwardIterator last, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		const size_t n = fc::min( N - m_size, (size_t)fc::distance(first, last) );
		ForwardIterator newLast = first;
		fc::advance( newLast, n );

		fc::copy_backward( pos, end(), end() + n );
		fc::copy( first, newLast, pos );
		m_size += n;
	}

	template <class InputIterator>
	void InsertIterator( iterator pos, InputIterator first, InputIterator last, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));

		const size_t n = fc::min( N - m_size, (size_t)fc::distance(first, last) );
		const size_t rpos = size_type(end() - pos);
		if( n <= rpos )
		{
			T* diff = end() - n;
			fc::uninitialized_copy( diff, end(), end() );
			fc::copy_backward( pos, diff, end() );
			fc::copy( first, last, pos );
		}
		else
		{
			fc::uninitialized_copy( pos, end(), end() + n - rpos );

			InputIterator mid = first;
			fc::advance( mid, rpos );
			fc::copy( first, mid, pos );
			fc::uninitialized_copy( mid, last, end() );
		}
		m_size += n;
	}

	void InsertValues( iterator pos, size_t n, const T& value, true_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		n = fc::min( N - m_size, n );

		const value_type tmp = value;
		fc::copy_backward( pos, end(), end() + n );
		fc::fill_n( pos, n, tmp );
		m_size += n;
	}

	void InsertValues( iterator pos, size_t n, const T& value, false_type )
	{
		FC_ASSERT(iterator_is_valid(pos));
		n = fc::min( N - m_size, n );

		const value_type tmp = value;
		const size_t rpos = size_type(end() - pos);
		if( n <= rpos )
		{
			iterator diff = end() - n;
			fc::uninitialized_copy( diff, end(), end() );
			fc::copy_backward( pos, diff, end() );
			fc::fill_n( pos, n, tmp );
		}
		else
		{
			fc::uninitialized_copy_backward( pos, end(), end() + n );
			fc::uninitialized_fill_n( end(), n - rpos, tmp );
			fc::fill_n( pos, rpos, tmp );
		}

		m_size += n;
	}

	buffer_type m_buffer;
	size_t m_size;

};



// global vector operators

template <class T, size_t U, size_t V> inline
	void swap( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		a.swap(b);
	}

template <class T, size_t U, size_t V> inline
	bool operator ==( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return( a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin()) );
	}

template <class T, size_t U, size_t V> inline
	bool operator !=( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return !(a == b);
	}

template <class T, size_t U, size_t V> inline
	bool operator <( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, size_t U, size_t V> inline
	bool operator >( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return b < a;
	}

template <class T, size_t U, size_t V> inline
	bool operator <=( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return !(b < a);
	}

template <class T, size_t U, size_t V> inline
	bool operator >=( const static_vector<T, U>& a, const static_vector<T, V>& b )
	{
		return !(a < b);
	}



FC_NAMESPACE_END
